\chapter{Resultados}
Las pruebas fueron realizadas siempre bajo las mismas condiciones y en la misma
computadora, la cual cuenta con un procesador Intel Core 2 Duo con dos núcleos
de 2.20GHz cada uno, 4GB de memoria RAM y sistema operativo Linux. La versión
de Java utilizada fue la 1.7.0\_25.\\

Los casos de pruebas utilizados para correr
los experimentos fueron obtenidos de dos fuentes: un gran set
de rompecabezas de diversos tamaños fue obtenido del sitio de ``International
Conference on Metaheuristics and Nature Inspired Computing (META)'', edición
2010 \cite{Meta10}, donde se realizó un concurso inspirado en el rompecabezas
Eternity II y, por otro lado, las piezas correspondientes al rompecabezas
EternityII fueron conseguidas a través de una red de intercambio de
archivos peer-to-peer y comprobada su validez a través del chequeo que ofrece
el programa \textit{E2Lab} \cite{E2lab}.\\

A continuación mostramos y analizamos los resultados que consideramos mas
relevantes del trabajo. En el apéndice \ref{app:resultados} pueden encontrarse
más resultados, incluyendo aquellos sobre los cuales se decidieron los valores 
de los parámetros del algoritmo y también algunos operadores alternativos que
fuimos probando durante la construcción del mismo. A menos que se indique lo
contrario, el caso de prueba utilizado en los resultados es el del rompecabezas
EternityII.\\

Se analizó la evolución del fitness de la
mejor solución de la población en función del tiempo de ejecución
del algoritmo medido en segundos. En la figura \ref{fig:fitness_normal} se
puede observar una comparación de este
comportamiento entre el algoritmo evolutivo con búsqueda local y una
versión del mismo sin búsqueda local. En el gráfico \ref{fig:fitness_log} se
utilizó escala logarítmica en el tiempo para una mejor lectura y comprensión de
los datos.

\begin{figure}[H]
\centering
\subfigure[Escala normal]{
	\includegraphics[width=0.7\textwidth]{imagenes/fitness_iteraciones_c.pdf}
	\label{fig:fitness_normal}
}
\\
\subfigure[Escala logarítmica]{
	\includegraphics[width=0.7\textwidth]{imagenes/fitness_iteraciones_c_l.pdf}
	\label{fig:fitness_log}
}
\caption{Comparación del comportamiento entre implementaciones}
\label{fig:comparacion_fitness}
\end{figure}

En ambas series de datos puede observarse que el crecimiento del fitness es muy
marcado hasta los primeros 10 segundos y luego continúa creciendo paulatinamente
hasta los 100 segundos para finalmente estabilizarse. El algoritmo con búsqueda
local consigue en todo momento soluciones mejores respecto al algoritmo sin 
la modificación, incluso llegando a soluciones por arriba de los 400 puntos de
fitness en menos de 100 segundos.
También puede observarse, en el comportamiento del algoritmo con búsqueda local,
incrementos en forma de pequeños saltos de su fitness, que se van haciendo menos
frecuentes a lo largo del tiempo pero que aún, cercano a los 500 segundos siguen
sucediendo. Este comportamiento es clave en el funcionamiento del algoritmo y
fue lo que nos motivó, además del incremento del fitness, a implementar el uso
de búsqueda local.
\\

Con el fin de comprender mejor el comportamiento en forma de saltos
anteriormente mencionado, se decidió cuantificar el concepto de similitud
entre dos soluciones. Para esto, definimos la similitud de dos soluciones de la
siguiente manera: Dadas dos soluciones $X1$ y $X2$ de tamaño $n \times n$,

\begin{displaymath}
similitud(X1, X2) = \frac{\sum_{\substack{0 \leq i \leq n \\ 0 \leq j < n}}
f(x1_{i,j}, x2_{i,j})} {n \times n}\\
\end{displaymath}  

\noindent donde

\begin{displaymath}
f(x1, x2) = 
\left\{ \begin{array}{l l}
1	&	\mbox{si } \Pi_t(x1) = \Pi_t(x2) \land \Pi_r(x1) = \Pi_r(x2)\\
	&	\land \Pi_b(x1) = \Pi_b(x2) \land \Pi_l(x1) = \Pi_l(x2) \\
0	&	cc. 
\end{array} \right.
\end{displaymath}\\

Es decir, la similitud es un valor real que va de 0 a 1 y depende de cuantas
piezas coinciden en posición y colores entre los dos rompecabezas comparados.
Cuanto más cercano a 1 es este valor mayor similitud tienen las
soluciones.\\

La tabla \ref{tab:fragmento_ejecucion} muestra parte de los registros de una
ejecución del algoritmo.\\

\begin{table}[H]
\centering
\begin{tabular}{|r|r|r|}
\hline
\multicolumn{1}{|l|}{Iteracion} & \multicolumn{1}{l|}{Fitness} & \multicolumn{1}{l|}{Similitud} \\ \hline
9400 & 410 & 1 \\ 
9500 & 413 & 0.4 \\
9600 & 413 & 1 \\
9700 & 413 & 0.87 \\ 
9800 & 413 & 0.98 \\ 
9900 & 413 & 1 \\ 
10000 & 415 & 0.81 \\ 
10100 & 415 & 1 \\ 
10200 & 415 & 1 \\ 
\multicolumn{1}{|c|}{\vdots} & \multicolumn{1}{c|}{\vdots} &
\multicolumn{1}{c|}{\vdots}\\ 
24900 & 418 & 1 \\ 
25000 & 418 & 1 \\ 
25100 & 419 & 0.17 \\ 
25200 & 419 & 1 \\ 
25300 & 420 & 0.93 \\
25400 & 420 & 1 \\
25500 & 420 & 1 \\ 
25600 & 420 & 1 \\ \hline
\end{tabular}
\caption{Fragmento de ejecución que muestra la mejor solución conseguida hasta
el momento}
\label{tab:fragmento_ejecucion}
\end{table}

En la primer columna se encuentra el número de iteración, la segunda el fitness del mejor individuo que
se encuentra en la población en esa iteración y la tercera la similitud de ese
individuo respecto del mejor individuo del registro anterior. Puede observarse
que cuando no se encuentra una mejor solución, la similitud es generalmente 1,
es decir, la mejor solución generalmente sigue siendo la misma que en el
registro anterior aunque puede tratarse de otra solución del mismo fitness que
la anterior pero distinta como es el caso de las iteraciones 9600, 9700 y 9800.\\

En el caso de que sí se encuentre una mejor solución, la similitud toma diversos
valores, a veces altos como en el caso de la iteración 10000 y a veces bajos 
como en el caso de la iteración 9500.
Un valor alto (siempre tomando en cuenta los casos distintos de 1)
generalmente significa que esa nueva solución es similar a la anterior pero con
algunas pequeñas modificaciones que pueden haber sido generadas por el operador
SwapMutationOperator o por la búsqueda local sobre la mejor solución. En cambio,
cuando el valor es bajo, menor al 80\%, puede tener dos significados: la mejora
proviene del operador crossover; o que la búsqueda local en alguna otra solución
hizo que la misma pase a tener importancia, ayudada por el factor de elitismo
del algoritmo. Es en este último caso donde se puede observar la mejora que
introduce la búsqueda local al algoritmo evolutivo. Esto puede explicarse
debido a que el algoritmo evolutivo permite diversificar las soluciones
explorando dentro del espacio de búsqueda y la búsqueda local hace resaltar las buenas soluciones dentro de esa
exploración. Este comportamiento puede incluso observarse luego de varios
minutos de ejecución, como es el caso de las iteraciones 25000 y 25100, y es el
que le da sentido al crecimiento escalonado que se observa en los gráficos
mostrados en la figura \ref{fig:comparacion_fitness}.\\

Si bien el algoritmo con la búsqueda local presenta, en este problema, siempre
mejores resultados que la implementación sin la misma, el costo a nivel
rendimiento es considerablemente alto tal como se muestra en la figuura
\ref{fig:rendimiento}.\\

\begin{figure}[H]
\centering
\includegraphics[width=0.7\textwidth]{imagenes/iteraciones_segundos.pdf}
\caption{Comparación del tiempo entre implementaciones}
\label{fig:rendimiento}
\end{figure}
 
La figura muestra la cantidad de iteraciones en escala logarítmica en función
del tiempo de ejecución medido en segundos para tres versiones distintas del
algoritmo:
sin búsqueda local, con una búsqueda local simple sin ejecuciones en paralelo y
con la búsqueda local finalmente implementada que, para nuestro caso
particular, posee una cantidad de 2 hilos de ejecución.\\

Se observa claramente que los algoritmos con
búsqueda local iteran muchas menos veces, en relación de 1 a 10 respecto a la
misma versión pero sin la búsqueda local. Asimismo, puede observarse una
importante mejora en la utilización de threads relativo a la misma
implementación, pero con un solo hilo de ejecución, aunque la misma parece
despreciable respecto a la implementación sin la heurística local. Igualmente, y
teniendo en cuenta las arquitecturas de las PCs contemoporáneas, debería ser
posible mejorar mucho más este resultado configurando más hilos de ejecución y
sin la necesidad de recurrir a sistemas distribuidos.
Como se comentó anteriormente, este aspecto no resultó limitante ya que aún con
la desventaja del rendimiento, hemos conseguido mejores resultados con la
implementación de varios hilos y fundamentalmente, un mejor comportamiento  del
algoritmo.\\
La variación del rendimiento del algoritmo respecto a las diferentes
instancias puede resumirse en el gráfico comparativo que se observa en la
figura \ref{fig:comparacion_rendimiento}.

\begin{figure}[H]
\centering
\includegraphics[width=0.7\textwidth]{imagenes/segundos_iteraciones_all.pdf}
\caption{Comparación del tiempo entre instancias}
\label{fig:comparacion_rendimiento}
\end{figure}

La figura \ref{fig:comparacion_rendimiento} compara las iteraciones en
función del tiempo medido en segundos para las instancias $10 \times 10$, $12 \times 12$, $14 \times 14$ y $16 \times 16$.
Como era esperado, puede observarse que a medida que se incrementa el tamaño de
la instancia, disminuye la cantidad de iteraciones, es decir, el tiempo en
completar cada iteración es mayor. Se debe considerar en el análisis de
estos resultados que el incremento de piezas por instancia
no es lineal sino que polinómico ($n^2$).\\

A continuación analizamos los resultados finales obtenidos sobre las diferentes
ins\-tan\-cias incluyendo al EternityII (tabla \ref{tab:finales}). Los datos
corresponden a 10 ejecuciones independientes del algoritmo. Se estableció un
límite de 128000 iteraciones por ejecución dado que el tiempo que demanda es
suficiente para alcanzar una estabilidad en el algoritmo como se mostró en la
 figura \ref{fig:comparacion_fitness}.\\
 
\begin{table}[H]
\centering
\begin{tabular}{|r|r|r|r|r|r|r|}
\hline
\multicolumn{1}{|l|}{Instancia} & \multicolumn{1}{l|}{Max Sol Posible} &
\multicolumn{1}{l|}{Iteraciones} & \multicolumn{1}{l|}{Mejor Sol} &
\multicolumn{1}{l|}{Duracion (seg)} & \multicolumn{1}{l|}{ES} &
\multicolumn{1}{|l|}{VS} 
\\ \hline
6x6 & 60 & 57041 & 60 & 42.7 & 59.8 & 0.40 \\ 
7x7 & 84 & 128000 & 81 & 183.2 & 80.6 & 0.27 \\ 
10x10 & 180 & 128000 & 165 & 281.9 & 162.6 & 2.49 \\ 
12x12 & 264 & 128000 & 239 & 378.1 & 234.8 & 6.18 \\ 
14x14 & 364 & 128000 & 321 & 531.0 & 318.2 & 5.07 \\ 
16x16 \footnotemark[1]& 480 & 128000 & 431 & 626.7 & 426.3 & 8.23
\\
\hline
\end{tabular}
\caption{Resultados finales en las diferentes instancias}
\label{tab:finales} 
\end{table}

\footnotetext[1]{Instancia correspondiente al rompecabezas EternityII}

La primera columna corresponde a la instancia; la segunda indica el máximo valor
que el fitness puede tomar para esa instancia y que correspondería a una
solución exacta del rompecabezas; la tercera columna muestra el promedio de
iteraciones ejecutadas; la siguiente corresponde al fitness de la mejor solución conseguida
en las 10 ejecuciones; la quinta columna muestra el promedio de tiempo necesario
para cumplir con la totalidad de las iteraciones, expresado en segundos, y
las últimas dos columnas corresponden a la esperanza y a la varianza muestral
del fitness de las mejores soluciones obtenidas.\\

Lo primero que podemos observar es que la solución presentada resuelve en
aproximadamente 40 segundos el rompecabezas de $6 \times 6$ con una valor de
varianza bajo, lo que indica que lo resuelve casi la totalidad de las
veces. No se observa lo mismo en instancias más grandes ya que no ha sido
posible resolverlas de forma completa. Por ejemplo, en la instancia
correspondiente al Eternity II, la mejor solución encontrada fue de 431 con 
un promedio de 426, de un máximo posible de 480, lo que representa una mejora
considerable respecto a las soluciones presentadas por otros algoritmos
evolutivos, incluso utilizando un tiempo hasta 6 veces menor en algunas ocasiones (Ver trabajos
relacionados en sección \ref{et:relacionados}).
\\

Otro resultado de interés que se desprende de la tabla \ref{tab:finales}
corresponde a los porcentajes de completitud que en promedio se han conseguido. La
siguiente tabla resume este dato: \\

\begin{table}[H]
\centering
\begin{tabular}{|r|r|}
\hline
\multicolumn{1}{|l|}{Instancia} & \multicolumn{1}{l|}{Completitud}
\\ \hline
6x6 & 99.7\% \\ 
7x7 & 96.0\% \\ 
10x10 & 90.3\% \\ 
12x12 & 88.9\% \\ 
14x14 & 87.4\%  \\ 
16x16 & 88.8\%
\\
\hline
\end{tabular}
\caption{Porcentajes de completitud promedio de las diferentes instancias}
\label{tab:finales_pct}
\end{table}

Se observa en la tabla \ref{tab:finales_pct} que en todos los casos el
porcentaje de completitud promedio supera el 87\%, es decir, más del 87\% del
rompecabezas ha sido resuelto. Este dato es considerablemente mayor para las
instancias de menor tamaño.\\

A continuación mostramos las imágenes de dos soluciones encontradas:
una perteneciente a la instancia $6 \times 6$ resuelta de forma completa; la
otra a la mejor solución encontrada para la instancia correspondiente al Eternity II:\\

\begin{figure}[H]
\centering
\includegraphics[width=0.8\textwidth]{imagenes/final_6x6.pdf}
\caption{Mejor solución en instancia $6 \times 6$ (60/60)}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[width=0.7\textwidth]{imagenes/final_e2_v.pdf}
\caption{Mejor solución del EternityII (431/480)}
\end{figure}

Para concluir esta sección, mostramos una
comparación entre nuestros resultados obtenidos sobre la instancia $16x16$,
correspondiente al EternityII, y aquellos conseguidos por los trabajos
relacionados dentro del campo de las metaheurísticas, comentados en la
sección \ref{et:relacionados}.\\

\begin{table}[H]
\centering
\begin{tabular}{|r|r|r|r|r|}
\hline
\multicolumn{1}{|l}{Mejor Solución} &
\multicolumn{1}{|l|}{Promedio} &
\multicolumn{1}{|l|}{Técnica} &  \multicolumn{1}{l|}{Autores}
 \\ \hline
396 & 392.5 & GA\footnotemark[1] & Muñoz y col.\\
418 & 408.6 & Tabu Search y SA\footnotemark[1] & Wei-Sin y col. \\ 
425 & 419.6 & VNS\footnotemark[1] & Coelho y col. \\ 
\textbf{431} & \textbf{426.3} & \textbf{GA\footnotemark[1] y Búsqueda Local} & 
\textbf{Tesis}
\\
458 & $\approx$ 440 & Contraint Programming y VLNS\footnotemark[1] & Schaus y
col.\\
459 & 456.4 & Hiper Heurísticas & Vancroonenburg y col.
\\
\hline
\end{tabular}
\caption{Comparación con trabajos relacionados}
\label{tab:finales_cmp}
\end{table}

\footnotetext[1]{GA = Genetic Algorithm; SA = Simulated Annealing; VNS =
Variable Neighborhood Search; VLNS = Very large-scale neighborhood search}

Teniendo en cuenta que los últimos casos no pertecen exclusivamente a técnicas relacionadas a las metaheurísticas, puede observarse que la solución presentada
en este trabajo tuvo un resultado favorable. \\

 Respecto al rendimiento temporal del algoritmo, no hemos podido
realizar una comparación directa de los resultados entre los diversos autores. Esto se debe
principalmente a que los mismos toman en cuenta distintos aspectos de
rendimiento. Algunos toman la cantidad de iteraciones, otros la cantidad de
veces que se evalúa la función de evaluación, otros el tiempo hasta conseguir la
mejor solución y en otros casos el tiempo límite que se ejecutó el algoritmo.
En el caso de Wei-Sin, Coelho y Schaus, el tiempo límite que se ejecutó el
algoritmo fué de 3600 segundos, 1 hora y 24 horas respectivamente. Para el
caso de Vancroonenburg la mejor solución se encontró a los 1005 segundos.
